public class diameterOfBinaryTree {
    /**
     * 二叉树的直径
     *
     * 给你一棵二叉树的根节点，返回该树的 直径 。
     *
     * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
     *
     * 两节点之间路径的 长度 由它们之间边数表示。
     *
     */
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.right = right;
            this.left = left;
        }
    }
    static int max = 0; //定义全局变量

    public static int method(TreeNode root){
        // 利用dfs
        if(root == null){
            return 0;
        }
        dfs(root);
        return max;
    }
    public static int dfs(TreeNode root){
        if(root.left == null && root.right == null){
            return 0;
        }
        int leftSize = root.left ==null ?0: dfs(root.left) + 1;
        int rightSize = root.right == null ?0: dfs(root.right) + 1;
        max = Math.max(max, leftSize + rightSize);
        return Math.max(leftSize, rightSize);
    }

    public static void main(String[] args) {
        diameterOfBinaryTree dd = new diameterOfBinaryTree();
        TreeNode node = dd.new TreeNode(1);

        node.left = dd.new TreeNode(2);
        node.right = dd.new TreeNode(2);
        node.left.left = dd.new TreeNode(4);
        node.left.right = dd.new TreeNode(5);
        node.right.left = dd.new TreeNode(5);
        node.right.right = dd.new TreeNode(4);

        int res = method(node);
        System.out.println("res = " + res);
    }

}


//    private int dfs(TreeNode root) {
//        if (root.left == null && root.right == null) {
//            return 0;
//        }
//        int leftSize = root.left == null? 0: dfs(root.left) + 1;
//        int rightSize = root.right == null? 0: dfs(root.right) + 1;
//        max = Math.max(max, leftSize + rightSize);
//        return Math.max(leftSize, rightSize);
//    }
//}